Service providers and device manufacturers (e.g., wireless, cellular, etc.) are continually challenged to deliver value and convenience to consumers by, for example, providing compelling network services. One area of interest has been the development of mapping and/or navigation applications that provide users of mobile devices (e.g., mobile phones, tablets, phablets, personal navigation devices (PNDs), etc.) with substantially real-time location-based information to assist them with their travels. In particular, users often want to know the shortest path (e.g., in terms of distance, time, fuel consumption, etc.) between an origin (e.g., a home) and a particular destination (e.g., an office, a restaurant, etc.). Currently, finding a route through a road network, for example, can be described by the common single-source path problem. For example, from the road network, an abstract model (e.g., a directed graph) can be generated where junctions are most often represented by nodes and streets are most often represented by edges and each is assigned a cost-function describing the weight for traversing the element. Consequently, the wanted solution of the shortest path problem is a path through the graph from an origin node or edge to a destination node or edge where the sum of all costs is minimal. Such a path with minimal cost is also referred to as shortest path through the graph.
However, current routing calculations are often inaccurate due to the underlying static network model and the current method of detecting of travel time. Firstly, because current solutions are generally based on a static graph created upon a road network, when the network changes from time to time (e.g., as a result of construction, road closure, etc.), such routing calculations can quickly become outdated and therefore inaccurate. Moreover, updating/maintaining static routing models (“routable road maps”) is generally time consuming and costly. Secondly, there are several issues that bias current travel time estimations, for example, the accuracy of traffic state detection on edges and the accuracy of travel time information on nodes of the static graph model. In particular, detection of current travel times on the edges is largely done by local detectors embedded on selected locations in the road surface. Consequently, resulting travel times over roads and the abstracted model have to be estimated from the local detection by extrapolation rather than using real-time transit time measurement results. In addition, the real-time travel time estimates and traffic incidents broadcast (e.g., via Traffic Message Channel (TMC, ISO 14819)) mostly cover important and higher-ranked roads only. Therefore, there is also a lack of traffic data for inner-TMC-location edges and interchanges not mapped by the TMC. Accordingly, service providers and device manufacturers face significant technical challenges in offering a service that provides routing calculations based on geographical positioning data from one or more mobile devices (i.e., probes) independent of (possibly outdated) map data and (imprecise/incomplete) TMC data.